class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):  # O(n+m)
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        if len(nums1) == 0 and len(nums2) == 0:
            return "No median for empty lists!"
        
        n1 = len(nums1)
        n2 = len(nums2)
        curr1 = 0
        curr2 = 0
        merged_list = []
        while curr1 < n1 and curr2 < n2:
            if nums1[curr1] < nums2[curr2]:
                merged_list.append(nums1[curr1])
                curr1 += 1
            else:
                merged_list.append(nums2[curr2])
                curr2 += 1
                
        if curr1 < n1:
            merged_list += nums1[curr1:]
        if curr2 < n2:
            merged_list += nums2[curr2:]
        
        if (n1 + n2) % 2 == 1:
            return float(merged_list[(n1+n2)//2])
        else:
            m = (n1+n2)//2
            return float((merged_list[m-1] + merged_list[m])/2)
        

if __name__ == "__main__":
    soln = Solution()
    print(soln.findMedianSortedArrays([], []))
    print(soln.findMedianSortedArrays([1,], []))
    print(soln.findMedianSortedArrays([], [2]))
    print(soln.findMedianSortedArrays([1, 2], [3]))
    print(soln.findMedianSortedArrays([0, 0], [0, 0]))
    print(soln.findMedianSortedArrays([1, 2], [3, 4]))
